
#include "BTreeNode.h"
#include <stdio.h>
#include <cstdlib>
#include <math.h>
#include <iostream>
#include <fstream>
#include <map>

using namespace std;

map<PageId, string> ourhashmap;


void BTLeafNode::leafSwap(char *arr, int i, int j) {
    int temp_key, *temp_rid;

    temp_rid = (int*) malloc(2 * sizeof (int));

    //key swap
    memcpy(&temp_key, (char*)arr + 4 * sizeof (int) +i * 3 * sizeof (int), sizeof (int));
    
    memcpy((char*)arr + 4 * sizeof (int) +i * 3 * sizeof (int), (char*)arr + 4 * sizeof (int) +j * 3 * sizeof (int), sizeof (int));
    memcpy((char*)arr + 4 * sizeof (int) +j * 3 * sizeof (int), &temp_key, sizeof (int));
  
    //rid swap
    memcpy(temp_rid, (char*)arr + 4 * sizeof (int) +i * 3 * sizeof (int) + sizeof (int), 2 * sizeof (int));
    memcpy((char*)arr + 4 * sizeof (int) +i * 3 * sizeof (int) + sizeof (int), (char*)arr + 4 * sizeof (int) +j * 3 * sizeof (int)+  sizeof (int), 2 * sizeof (int));
    memcpy((char*)arr + 4 * sizeof (int) +j * 3 * sizeof (int) + sizeof (int), temp_rid, 2 * sizeof (int));


}
 

void BTNonLeafNode::nonLeafSwap(char *arr, int i, int j) {
    int temp_key, temp_pid;

    //key swap
    memcpy(&temp_key, (char*)arr + 4 * sizeof (int) +i * 2 * sizeof (int), sizeof (int));
    memcpy((char*)arr + 4 * sizeof (int) +i * 2 * sizeof (int), (char*)arr + 4 * sizeof (int) +j * 2 * sizeof (int), sizeof (int));
    memcpy((char*)arr + 4 * sizeof (int) +j * 2 * sizeof (int), &temp_key, sizeof (int));

    //pid swap
    memcpy(&temp_pid, (char*)arr + 4 * sizeof (int) +i * 2 * sizeof (int) + sizeof (int), sizeof (int));
    memcpy((char*)arr + 4 * sizeof (int) +i * 2 * sizeof (int) + sizeof (int), (char*)arr + 4 * sizeof (int) +j * 2 * sizeof (int) + sizeof (int), sizeof (int));
    memcpy((char*)arr + 4 * sizeof (int) +j * 2 * sizeof (int) + sizeof (int), &temp_pid, sizeof (int));
 



}
 
RC BTLeafNode::leafSort(char *temp) {

    int i, j, count, ai, aj;
    memcpy(&count, (char*)temp + 2 * sizeof (int), sizeof (int));
    
    for (int i = 0; i < count; i++) {
        for (j = i + 1; j < count; j++) {

            memcpy(&ai, (char*)temp + 4 * sizeof (int) +i * 3 * sizeof (int), sizeof (int));
            memcpy(&aj, (char*)temp + 4 * sizeof (int) +j * 3 * sizeof (int), sizeof (int));
            
            if (ai > aj) {
                BTLeafNode::leafSwap(temp, i, j);
            }

        }
    }    

}

RC BTNonLeafNode::nonLeafSort(char *temp) {
    
   

    int i, j, count, ai, aj;
    
    memcpy(&count, (char*)temp + 2 * sizeof (int), sizeof (int));

    for (int i = 0; i < count; i++) {
        for (j = i + 1; j < count; j++) {

            //temp+3 ints (the metadata )+ 1 int (1st page id)
            memcpy(&ai, (char*)temp + 4 * sizeof (int) +i * 2 * sizeof (int), sizeof (int));
            memcpy(&aj, (char*)temp + 4 * sizeof (int) +j * 2 * sizeof (int), sizeof (int));

            if (ai > aj) {
                BTNonLeafNode::nonLeafSwap(temp, i, j);
            }

        }
      
    }
    
    for (i = 0; i < count; i++) {
        memcpy(&ai, (char*)temp + 4 * sizeof (int) +i * 2 * sizeof (int), sizeof (int));
        int temppid;
        memcpy(&temppid, (char*)temp + 4 * sizeof (int) +i * 2 * sizeof (int)+sizeof(int), sizeof (int));
         
    }


}

BTLeafNode::BTLeafNode(PageId ppid, PageId pid, PageId siblingId, char* tablename) {

    numkeys = 0;
    
    memcpy(buffer, &ppid, sizeof (int));
    memcpy((buffer + sizeof (int)), &pid, sizeof (int));
    memcpy((buffer + 2 * sizeof (int)), &numkeys, sizeof (int));
    memcpy((buffer + 3 * sizeof (int)), &siblingId, sizeof (int));

    ourhashmap[pid] = "L";

    ofstream f;
    
    char* hashname = (char*) malloc(sizeof (tablename) + 5);
    strcpy(hashname, tablename);
    strcat(hashname, ".txt");
    
    
    f.open(hashname, ios::app);
    f.seekp(0, ios::end);
    f << pid << "\n" << ourhashmap[pid] << "\n";
    f.close();
}

/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::read(PageId pid, const PageFile& pf) {

    return 0;
}

/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::write(PageId pid, PageFile& pf) {

    return 0;
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTLeafNode::getKeyCount() {
    return 0;
}

/*
 * Insert a (key, rid) pair to the node.
 * @param key[IN] the key to insert
 * @param rid[IN] the RecordId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
int BTLeafNode::insert(int key, const RecordId& rid, PageFile &pf, PageId rootPid, char* tablename) {
    
    
    char temp[1024], parentBuffer[1024], nodeToInsert_buffer[1024];
    int key_pushed, currentNumberOfKeys;
    PageId cursor;
    int newroot, oldNodeCount, parentid;
    
//    temp = malloc(100*sizeof(int));
//    parentBuffer = malloc(100*sizeof(int));
//    nodeToInsert_buffer = malloc(100*sizeof(int));
    
    pf.read(rootPid, temp);
    
    //modify temp here to include the new (key,pid,sid) triple

    memcpy(&oldNodeCount, (char*)temp + 2 * sizeof (int), sizeof (int));
    
    if (ourhashmap[rootPid] == "L") {

        if (oldNodeCount < MAX_LEAF) {
            
            memcpy((char*)temp + 4 * sizeof (int) +  oldNodeCount * 3 * sizeof (int), &key, sizeof (int));
            memcpy(((char*)temp + 4 * sizeof (int) + oldNodeCount * 3 * sizeof (int) + sizeof (int)), &rid, (2 * sizeof (int)));
            oldNodeCount++;
            memcpy((char*)temp + 2 * sizeof (int) , &oldNodeCount, sizeof (int));
            newroot = 0;
            BTLeafNode::leafSort((char*)temp);
            
        } else {

            //special case of insert and split
            
            int newNodeId = pf.endPid();
            int newPPid = -1, newSiblingId = -1;
            BTLeafNode newSplitNode(newPPid, newNodeId, newSiblingId, tablename);

            memcpy((char*)temp + 4 * sizeof (int) +oldNodeCount * 3 * sizeof (int), &key, sizeof (int));
            memcpy(((char*)temp + 4 * sizeof (int) +oldNodeCount * 3 * sizeof (int) + sizeof (int)), &rid, (2 * sizeof (int)));

            // sort(temp);
            int newIncrValue = oldNodeCount+1;
            memcpy((char*)temp + 2 * sizeof (int), &newIncrValue, sizeof (int));
             
            BTLeafNode::leafSort((char*)temp);
            

            /**
             * INSERT AND SPLIT FUNCTION CODE BELOW:
             * prevNodeCount:Now how much will remain in old node
             * newNodeCount: how many in new node
             */

            int prevNodeCount = (int)ceil((oldNodeCount + 1) / 2);
            int newNodeCount = oldNodeCount - prevNodeCount + 1;


            /*Copying the metadata into the old node and the newly split node*/
            memcpy((char*)temp + 2 * sizeof (int), &prevNodeCount, sizeof (int));
            memcpy(newSplitNode.buffer + 2 * sizeof (int), &newNodeCount, sizeof (int));
            memcpy((char*)temp + 3 * sizeof (int), &newNodeId, sizeof (int));


            int our_index = ((prevNodeCount ) * sizeof (int) * 3) + 4 * sizeof (int), j = 4 * sizeof (int);

            while (our_index <= (MAX_LEAF + 1)*3 * sizeof (int) + 4 * sizeof (int)) {
                /*
                 * first iteration. key_pushed variable 
                 * contains the 1st data of the new node, 
                 * which needs to be copied to the parent
                 */
                if (j == 4 * sizeof (int)) {
                    memcpy(&key_pushed, (char*)temp + our_index, sizeof (int));
                }

                memcpy(newSplitNode.buffer + j, (char*)temp + our_index, 3 * sizeof (int));

                our_index += 3 * sizeof (int);

                j += 3 * sizeof (int);

            }

            pf.write(newNodeId, newSplitNode.buffer);
             
            newroot = pf.endPid();

            BTNonLeafNode btnl (-1, newroot, tablename);

            btnl.initializeRoot(rootPid, key_pushed, newNodeId);
            memcpy((char*)temp, &newroot, sizeof (int));
            
            
            memcpy(newSplitNode.buffer, &newroot, sizeof (int));
            
            pf.write(newroot, btnl.getBuffer());
            pf.write(newNodeId, newSplitNode.buffer);
            
        }

        pf.write(rootPid, temp);

        rootPid = newroot;

    } else {   
        //general case for insert and split
        //ourhashmap['rootpid']='N'
        cursor = rootPid;

        while (ourhashmap[cursor] != "L") {
            BTNonLeafNode::locateChildPtr(key, cursor, pf);
        }
        /* now cursor has the page id of the leaf node in which we should insert
         * the Key.
         * Next we read the contents of the page (pointed to by cursor),
         * into nodeToInsert_buffer
         * 
         */
        pf.read(cursor, nodeToInsert_buffer);
        


        memcpy(&currentNumberOfKeys, (char*)nodeToInsert_buffer + 2 * sizeof (int), sizeof (int));

        if (currentNumberOfKeys < MAX_LEAF) {
            //insert into this node and sort
 
            memcpy((char*)nodeToInsert_buffer + 4 * sizeof (int) +currentNumberOfKeys * 3 * sizeof (int), &key, sizeof (int));
            memcpy(((char*)nodeToInsert_buffer + 4 * sizeof (int) +currentNumberOfKeys * 3 * sizeof (int) + sizeof (int)), &rid, (2 * sizeof (int)));
            
            int temp_key = currentNumberOfKeys+1;
            memcpy((char*)nodeToInsert_buffer + 2 * sizeof (int), &temp_key, sizeof (int));
            
            BTLeafNode::leafSort((char*)nodeToInsert_buffer);
            //SORT!!!

        } else {
            //insert and split


            /****************************************************************/

            
            int newNodeId = pf.endPid();
            int newPPid = -1, newSiblingId = -1;

            BTLeafNode newSplitNode(newPPid, newNodeId, newSiblingId, tablename);

            memcpy((char*)nodeToInsert_buffer + 4 * sizeof (int) +currentNumberOfKeys * 3 * sizeof (int), &key, sizeof (int));

            memcpy(((char*)nodeToInsert_buffer + 4 * sizeof (int) +currentNumberOfKeys * 3 * sizeof (int) + sizeof (int)), &rid, (2 * sizeof (int)));
            // sort(temp);
            int newIncrValue = currentNumberOfKeys+1;
            memcpy((char*)nodeToInsert_buffer + 2 * sizeof (int), &newIncrValue, sizeof (int));
            
            BTLeafNode::leafSort((char*)nodeToInsert_buffer);

            /**
             * INSERT AND SPLIT FUNCTION CODE BELOW:
             * prevNodeCount:Now how much will remain in old node
             * newNodeCount: how many in new node
             */

            int prevNodeCount = (int)ceil((currentNumberOfKeys + 1) / 2);

            int newNodeCount = currentNumberOfKeys - prevNodeCount + 1;
            
            //call the insert and split function here
            int numberOfParentElements = BTLeafNode::insertAndSplit(prevNodeCount, parentid, newNodeCount,
                    newNodeId, newSplitNode, nodeToInsert_buffer, cursor, pf);

            //NOW CHECK FOR NON LEAF OVERFLOW
            if (numberOfParentElements > MAX_NONLEAF) {
                // INSERT AND SPLIT NON LEAF
                BTNonLeafNode::insertAndSplit(parentid, pf, rootPid, tablename);

            }


        }
        pf.write(cursor, nodeToInsert_buffer);
    }

    return rootPid;

}

/*
 * Insert the (key, rid) pair to the node
 * and split the node half and half with sibling.
 * The first key of the sibling node is returned in siblingKey.
 * @param key[IN] the key to insert.
 * @param rid[IN] the RecordId to insert.
 * @param sibling[IN] the sibling node to split with. This node MUST be EMPTY when this function is called.
 * @param siblingKey[OUT] the first key in the sibling node after split.
 * @return 0 if successful. Return an error code if there is an error.
 */

/* ----OLD insertAndSplit Definition-- Given by Chu-Cheng
 * RC BTLeafNode::insertAndSplit(int key, const RecordId& rid,
        BTLeafNode& sibling, int& siblingKey) 
 */

RC BTLeafNode::insertAndSplit(int prevNodeCount, PageId &parentid, int newNodeCount, PageId newNodeId, BTLeafNode newSplitNode,
    char *nodeToInsert_buffer, int cursor, PageFile &pf) {
 
    int old_sibling_id, key_above;
    char parentBuffer[1024];

    /*Copying the Metadata into my old and new leaf nodes
     */

    memcpy((char*)nodeToInsert_buffer + 2 * sizeof (int), &prevNodeCount, sizeof (int));

    memcpy(newSplitNode.buffer + 2 * sizeof (int), &newNodeCount, sizeof (int));

    /*setting the sibling ids of the old and new node
     */
    memcpy(&old_sibling_id, (char*)nodeToInsert_buffer + 3 * sizeof (int), sizeof (int));

    memcpy((char*)nodeToInsert_buffer + 3 * sizeof (int), &newNodeId, sizeof (int));

    memcpy(newSplitNode.buffer + 3 * sizeof (int), &old_sibling_id, sizeof (int));

    int our_index = ((prevNodeCount) * sizeof (int) * 3) + 4 * sizeof (int), j = 4 * sizeof (int);
  
    /*Our_Index : Points to the Middle of the Old Node
     * we take this Our_index to the End of the Old node and copy these elements
     * into the new node
     */
    while (our_index <= (MAX_LEAF + 1)*3 * sizeof (int) + 4 * sizeof (int)) {
        if (j == 4 * sizeof (int)) //first iteration
        {
            memcpy(&key_above, (char*)nodeToInsert_buffer + our_index, sizeof (int));
        }

        memcpy(newSplitNode.buffer + j, (char*)nodeToInsert_buffer + our_index, 3 * sizeof (int));

        our_index += 3 * sizeof (int);

        j += 3 * sizeof (int);
    }

    /***DONE WITH THE COPY OF HALF THE ELEMENTS****/

    /*Setting the new node's parent ID to the old node's parent ID*/
    memcpy(&parentid, (char*)nodeToInsert_buffer, sizeof (int));

    memcpy(newSplitNode.buffer, &parentid, sizeof (int));


    /*Writing the data back to the DISK*/

    pf.write(cursor, (char*)nodeToInsert_buffer);
    pf.write(newNodeId, newSplitNode.buffer);

    /****************************************************************/
    int numberOfParentElements = BTNonLeafNode::insert(key_above, newNodeId,
            parentid, pf);










    return numberOfParentElements;
}

/*
 * Find the entry whose key value is larger than or equal to searchKey
 * and output the eid (entry number) whose key value >= searchKey.
 * Remeber that all keys inside a B+tree node should be kept sorted.
 * @param searchKey[IN] the key to search for
 * @param eid[OUT] the entry number that contains a key larger than or equalty to searchKey
 * 
 * @return 0 if successful. Return an error code if there is an error.
 * -1 : NO RECORDS FOUND. EQUALITY CASE
 * -1000 : INEQUALITY CONDITION SATISFIED
 
 */
RC BTLeafNode::locate(int searchKey, int& eid, PageId pid, PageFile &pf, char* indexname) {
    
    int j = 0, tempKey, number_of_keys, siblingId;
    
    char leafBuf[1024];
    
    ifstream mf;
    mf.open(indexname, ios::in);
    int sf = pf.open(indexname, 'r');

    pf.read(pid, leafBuf);
    
    memcpy(&number_of_keys, (char*)leafBuf + (2 * sizeof (int)), sizeof (int));
    //case for equality

        memcpy(&tempKey, (char*)leafBuf + 4 * sizeof (int), sizeof (int));

        while (tempKey < searchKey) 
        {

            memcpy(&tempKey, (char*)leafBuf + 4 * sizeof (int) +(j + 1)* 3 * sizeof (int), sizeof (int));
            j += 1;

            if (j >= number_of_keys) {
                eid = j+1;
                return EQUALITY_NOT_SATISFIED_OVERFLOW; //this is Equality case. and no records found.
            }
        }

        eid = j + 1;
        if (tempKey == searchKey) 
        {
            return EQUALITY_SATISFIED;
        }
        else
        {
            return EQUALITY_NOT_SATISFIED;
        }

   
}

/*
 * Read the (key, rid) pair from the eid entry.
 * @param eid[IN] the entry number to read the (key, rid) pair from
 * @param key[OUT] the key from the entry
 * @param rid[OUT] the RecordId from the entry
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::readEntry(int eid, int& key, RecordId& rid, PageId pid, PageFile pf) {

    void *leafBuf;
    
    pf.read(pid, leafBuf);
    memcpy(&rid, (char*)leafBuf + 4 * sizeof (int) +(eid - 1) * 2 * sizeof (int) + sizeof (int), 2 * sizeof (int));

    return 0;

}

/*
 * Return the pid of the next slibling node.
 * @return the PageId of the next sibling node 
 */
PageId BTLeafNode::getNextNodePtr() {
    return 0;
}

/*
 * Set the pid of the next slibling node.
 * @param pid[IN] the PageId of the next sibling node 
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::setNextNodePtr(PageId pid) {
    return 0;
}

/**
 * Constructor
 * @param ppid
 * @param pid
 * @return 
 */
 BTNonLeafNode::BTNonLeafNode(PageId ppid, PageId pid, char* tablename) {
    numkeys = 0;
    memcpy(buffer, &ppid, sizeof (int));
    memcpy(buffer + sizeof (int), &pid, sizeof (int));
    memcpy(buffer + 2 * sizeof (int), &numkeys, sizeof (int));
    ourhashmap[pid] = "N";

    ofstream f;
    
    char* hashname = (char*) malloc(sizeof (tablename) + 5);
    strcpy(hashname, tablename);
    strcat(hashname, ".txt");
    
    f.open(hashname, ios::app);
    f.seekp(0, ios::end);
    f << pid << "\n" << ourhashmap[pid] << "\n";
    f.close();





}

/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::read(PageId pid, const PageFile& pf) {
    return 0;
}

/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::write(PageId pid, PageFile& pf) {
    return 0;
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTNonLeafNode::getKeyCount() {
    return 0;
}

/*
 * Insert a (key, pid) pair to the node.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */

int BTNonLeafNode::insert(int key_above, PageId newNodeId, PageId parentid, PageFile &pf) {
    char parentBuffer[1024];
    int numberOfParentElements;

    pf.read(parentid, parentBuffer);

    memcpy(&numberOfParentElements, (char*)parentBuffer + 2 * sizeof (int), sizeof (int));

    //copy the Key_above variable and new page id into the parent Node
    memcpy((char*)parentBuffer + 4 * sizeof (int) +numberOfParentElements * 2 * sizeof (int), &key_above, sizeof (int));
    memcpy((char*)parentBuffer + 4 * sizeof (int) +numberOfParentElements * 2 * sizeof (int) + sizeof (int), &newNodeId, sizeof (int));
    //increase the number of parent elements by 1
    numberOfParentElements += 1;
    memcpy((char*)parentBuffer + 2 * sizeof (int), &numberOfParentElements, sizeof (int));
    //SORT
    BTNonLeafNode::nonLeafSort(parentBuffer);
 
    

    pf.write(parentid, parentBuffer);
     
    return numberOfParentElements;






}

/*
 * Insert the (key, pid) pair to the node
 * and split the node half and half with sibling.
 * The middle key after the split is returned in midKey.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @param sibling[IN] the sibling node to split with. This node MUST be empty when this function is called.
 * @param midKey[OUT] the key in the middle after the split. This key should be inserted to the parent node.
 * @return 0 if successful. Return an error code if there is an error.
 */

RC BTNonLeafNode::insertAndSplit(PageId pid, PageFile &pf, PageId &rootPid, char* tablename) {

    char oldNodeBuffer[1024], grandParentBuffer[1024];
    int  newPageid, midindex, numberofrecords, midkey;
    PageId parentid;
    int j = 0, our_index;

    pf.read(pid, oldNodeBuffer);
    memcpy(&parentid, (char*)oldNodeBuffer, sizeof (int));

    newPageid = pf.endPid();

    BTNonLeafNode newSplitNode (parentid, newPageid, tablename);

    memcpy(&numberofrecords, (char*)oldNodeBuffer + 2 * sizeof (int), sizeof (int));
    
    midindex = (int)ceil((numberofrecords + 1) / 2);

    memcpy(&midkey, (char*)oldNodeBuffer + 4 * sizeof (int) + (midindex - 1) * 2 * sizeof (int), sizeof (int));
    //memcpy(&our_index, (char*)oldNodeBuffer + 4 * sizeof (int) +midindex * 2 * sizeof (int) - sizeof (int), sizeof (int));
    j = 3 * sizeof (int);
 
    our_index = 3+ (midindex*2);
    
    while (our_index <= (3+(MAX_NONLEAF+1)* 2)) {
        
        
        memcpy(newSplitNode.buffer + j, (char*)oldNodeBuffer + our_index*sizeof(int), sizeof (int));
          
        int copiedkey;
        memcpy(&copiedkey, (char*)oldNodeBuffer + our_index*sizeof(int), sizeof(int));
        
        our_index ++;

        j += sizeof (int);
        
    }

    int newNodeCount = numberofrecords - midindex;
    int finalMidIndex = midindex - 1;

    
    memcpy((char*)oldNodeBuffer + 2 * sizeof (int), &finalMidIndex, sizeof (int));
    memcpy(newSplitNode.buffer + 2 * sizeof (int), &newNodeCount, sizeof (int));

    //Writing back the modified NonLeaf Pages to DISK
    pf.write(pid, oldNodeBuffer);
    pf.write(newPageid, newSplitNode.buffer);

    /* NOW OUR NON LEAF NODES are COMMITTED */

    /***MODIFYING THE PARENT IDs OF THE CHILD NODES TO newSplitNode.buffer's pageID***/

    int i = 0, childPid;
    char childBuffer[1024];

    while (i <= newNodeCount) {
        
        //POSSIBLE BUG: EXTRA DUE TO <= SIGN.
        
        memcpy(&childPid, newSplitNode.buffer + 3 * sizeof (int) +i * 2 * sizeof (int), sizeof (int));
        pf.read(childPid, childBuffer);
        memcpy((char*)childBuffer, &newPageid, sizeof (int));
        
        
        pf.write(childPid, childBuffer);
        i++;
    }

    int grandParentCount;
    if (pid == rootPid) {
        //NO ROOT ABOVE
        int newRootid = pf.endPid();
        BTNonLeafNode newRoot (-1, newRootid, tablename);

        memcpy(newRoot.buffer + 3 * sizeof (int), &pid, sizeof (int));
        memcpy(newRoot.buffer + 4 * sizeof (int), &midkey, sizeof (int));
        memcpy(newRoot.buffer + 5 * sizeof (int), &newPageid, sizeof (int));

        rootPid = newRootid;

        pf.write(rootPid, newRoot.buffer); 
  
    } else {
        /*NOW Push it up and check for recursion*/
        pf.read(parentid, grandParentBuffer);

        memcpy(&grandParentCount, (char*)grandParentBuffer + 2 * sizeof (int), sizeof (int));

        memcpy((char*)grandParentBuffer + 4 * sizeof (int) +(grandParentCount - 1)*2 * sizeof (int), &midkey, sizeof (int));
        memcpy((char*)grandParentBuffer + 4 * sizeof (int) +(grandParentCount - 1)*2 * sizeof (int) + sizeof (int), &newPageid, sizeof (int));
        grandParentCount++;
        memcpy((char*)grandParentBuffer + 2 * sizeof (int), &grandParentCount, sizeof (int));

        BTNonLeafNode::nonLeafSort(grandParentBuffer);

        if (grandParentCount > MAX_NONLEAF) {

            BTNonLeafNode::insertAndSplit(parentid, pf, rootPid, tablename);
        }
    }






    return 0;

}

/*
 * Given the searchKey, find the child-node pointer to follow and
 * output it in pid.
 * @param searchKey[IN] the searchKey that is being looked up.
 * @param pid[OUT] the pointer to the child node to follow.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::locateChildPtr(int searchKey, PageId& pid, PageFile &pf) {
            
    int j = 0, tempKey, number_of_keys;
    char nonLeafBuf[1024];
    
    pf.read(pid, nonLeafBuf);
    
    memcpy(&number_of_keys, (char*)nonLeafBuf + (2 * sizeof (int)), sizeof (int));
 
    memcpy(&tempKey, (char*)nonLeafBuf + 4 * sizeof (int), sizeof (int));
    
    while (tempKey <= searchKey) {
        //keep traversing
        memcpy(&tempKey, (char*)nonLeafBuf + 4 * sizeof (int) +(j + 1)*2 * sizeof (int), sizeof (int));
        j += 1;
        if (j >= number_of_keys)
            break;
    }

    memcpy(&pid, (char*)nonLeafBuf + 3 * sizeof (int) +j * 2 * sizeof (int), sizeof (int));






    return 0;
}

/*
 * Initialize the root node with (pid1, key, pid2).
 * @param pid1[IN] the first PageId to insert
 * @param key[IN] the key that should be inserted between the two PageIds
 * @param pid2[IN] the PageId to insert behind the key
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::initializeRoot(PageId pid1, int key, PageId pid2) {

    memcpy(buffer + 3 * sizeof (int), &pid1, sizeof (int));
    memcpy(buffer + 4 * sizeof (int), &key, sizeof (int));
    memcpy(buffer + 5 * sizeof (int), &pid2, sizeof (int));
    int count;
    memcpy(&count, buffer+2*sizeof(int), sizeof(int));
    count++;
    memcpy(buffer+2*sizeof(int), &count, sizeof(int));
    return 0;
}

